/*
  小乔在银行的一天
  题目描述
    小乔是一家银行的员工。
    今天银行照常开门营业，顾客们会陆陆续续来办业务，
    但是他们并不是按照进入银行的顺序办业务的，而是按照他们的 VIP 等级，并且对于每个顾客而言，办理完业务就会离开。
    小乔记录了银行营业一天中每一分钟具体发生的事件，可能是以下三种的其中一种：
      1. 让 VIP 等级最高的人办理业务；
      2. 让 VIP 等级最低的人办理业务；
      3. 进来了一个新顾客。
  输入
    第一行为一个数 n，表示银行一天营业的分钟数。
    往下 n 行，每行一个或者两个整数，
      其中第一个数（可能是 1,2,3）为事件的种类。若第一个数为 3，则还会有第二个整数表示进来的新顾客的 VIP 等级。
  输出
    对于每个办理业务的事件，输出一行，为一个整数表示办理业务的顾客的 VIP 等级。
    当然可能会存在这个时候没有顾客的情况，此时输出 -1。
  样例输入
    6
    3 4
    1
    2
    3 5
    3 7
    1
  样例输出
    4
    -1
    7
  数据范围
    n <= 500000，每个人的 VIP 等级 <= 5000000，且数据还保证不同顾客的 VIP 等级不同，以及每个顾客当天只会进银行一次。
*/

#include <bits/stdc++.h>

using namespace std;

/*
  说明:
    1. vector & set 应用场景分析
       通常我们认为 set 相比 vector的优势主要体现在"自动排序"和"去重"上!
       在如下场景下, 使用 set 比使用 vector 更好!
         a). 如果需要频繁地修改数据结构中的元素，并需要对数据结构中的元素进行排序;
         b). 或者不保证保存到数据结构中的一定是相同的单词.

    2. 当前题目应用分析
       本题中, 由于需要频繁地对数据结构进行修改, 并需要对数据结构中的元素进行排序,
       所以使用 set 相比 vector 更好!
*/
set <int> st;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int opt, x;

        cin >> opt;
        if (opt == 3) {         // 事件1: 进来一个新客户
            cin >> x;
            st.insert(x); // 事件进入等待集合中!
        } else if (opt == 2) {  // 事件2: 让 VIP 等级最低的人办理业务
            if (st.size() > 0) {
                // 从 set 中找到正常顺序下的第一个事件(vip等级最低)
                int v = *st.begin(); // 注意: st.rbegin() 表示正常顺序下的第一个元素的位置
                cout << v << endl;
                st.erase(v);
            } else {
                // set 为空, 即表示没有需要待处理的事件!
                cout << "-1" << endl;
            }
        } else {               // 事件3: 让 VIP 等级最高的人办理业务
            if (st.size() > 0) {
                /*
                  注意：
                    st.rbegin() 表示 reverse 顺序下的第一个元素的位置, 也就是正常顺序下的最后一个元素的位置
                    st.end() 表示正常顺序下的比 st.rbegin() 还要靠后一个元素的位置! 通常用该位置表示查找失败!
                */
                // 从 set 中找到正常数序下的最后一个事件(vip等级最高)
                int v = *st.rbegin();
                cout << v << endl;
                st.erase(v);
            } else {
                // set 为空, 即表示没有需要待处理的事件!
                cout << "-1" << endl;
            }
        }
    }

    return 0;
}